package com.ict.ycwl.pathcalculate.utils;

import com.ict.ycwl.pathcalculate.pojo.LngAndLat;
import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 86135
 */
@Component
public class ConvexHull {
    /**
     * 判断三个点的走向，用于确定是否是一个右转
     */
    private static int orientation(LngAndLat p, LngAndLat q, LngAndLat r) {
        double val = (q.getLatitude() - p.getLatitude()) * (r.getLongitude() - q.getLongitude()) -
                (q.getLongitude() - p.getLongitude()) * (r.getLatitude() - q.getLatitude());

        if (val == 0) {
            // 平行
            return 0;
        }
        // 右转或者左转
        return (val > 0) ? 1 : 2;
    }

    /**
     * 实现 Jarvis步进算法来计算凸包
     */
    public static List<LngAndLat> convexHull(LngAndLat[] points) {
        int n = points.length;
        if (n < 3) {
            // 至少需要三个点
            return null;
        }

        List<LngAndLat> hull = new ArrayList<>();

        // 找到最左边的点
        int leftMost = 0;
        for (int i = 1; i < n; i++) {
            if (points[i].getLongitude() < points[leftMost].getLongitude()) {
                leftMost = i;
            }
        }

        int p = leftMost, q;
        do {
            hull.add(points[p]);

            // 下一个点
            q = (p + 1) % n;

            for (int i = 0; i < n; i++) {
                if (orientation(points[p], points[i], points[q]) == 2) {
                    q = i;
                }
            }

            p = q;

        } while (p != leftMost);

        return hull;
    }
}
